Computational Complexity : A Modern Approach / Sanjeev Arora, Boaz Barak
By: Arora, Sanjeev [aut]
.
Contributor(s): Barak, Boaz [aut].
Cambridge : New York : Cambridge University Prees, 2009Edition: First edition.Description: xxiv, 579 pages : illustrated ; 25 cm.Content type: txt Media type: n Carrier type: ncISBN: 9780521424264.Subject(s): Computational complexity | Complejidad computacional | Criptografía | Lógica matemática (simbólica) | Computadores cuánticosDDC classification: 511.352 / | Item type | Current location | Collection | Call number | Copy number | Status | Notes | Date due | Barcode | Item holds |
|---|---|---|---|---|---|---|---|---|---|
Libros
|
Biblioteca Central | General | 511.352 / A769c (Browse shelf) | Ej. 1 | Available | CO | 8000021848 | ||
|
Libros
|
Biblioteca Central Book Cart | General | 511.352 / A769c (Browse shelf) | Ej. 2 | Available | 900000016496 |
Includes bibliographical references (p. 549-573) and indexes.
Notational conventions -- Basic Complexity Classes -- The computational model-and why it dosen´t matter -- NP and NP completeness -- Diagonalization -- Space complexity -- The polynomial hierarchy and alternations -- Boolean circuits -- Randomized computation -- Interactive proofs -- Crytography -- Quantum computation -- PCP theorem and hardness of approximation : An introduction -- Lower Bounds for Concrete Computational Models -- Communication complexity -- Circuit lower brounds : Complexity theory´s Waterloo -- Proof complexity -- Advanced topics -- Complexity of counting -- Average case complexity : Levin´s theory -- Hardness amplification and error-correcting codes -- Pseudorandom constructions : Expander and extractors -- Why are circuit lower bounds so difficult? -- Appendix : Mathematical background -- Bibliography --
Click on an image to view it in the image viewer
There are no comments for this item.